package com.zl.heap;

import java.beans.beancontext.BeanContext;

/**
 * @author zengle
 * @create 2021-05-29 22:51
 */
public class HeapSort {

    public void sortHeap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        heapInsert(arr);

        int len = arr.length - 1;
        while (len > 0) {
            swap(arr, 0, len);
            heapify(arr, 0, --len);
        }
    }

    private void heapInsert(int[] arr) {
        int last = arr.length - 1;
        for (int i = (last - 1) / 2; i >= 0; i--) {
            heapify(arr, i, last);
        }
    }

    private void heapify(int[] arr, int index, int len) {

        int left = index << 1 + 1;
        int right = left + 1;
        int largest = left;

        if (left > len) return;
        if (right <= len && arr[right] > arr[largest]) {
            largest = right;
        }
        if (arr[largest] > arr[index]) {
            swap(arr, index, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}
